// LeetCode 面试 Problem Ne. 02.01: 移除重复节点

/*
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:
	输入：[1, 2, 3, 3, 2, 1]
 	输出：[1, 2, 3]
示例2:
 	输入：[1, 1, 1, 1, 2]
 	输出：[1, 2]

提示：
    链表长度在[0, 20000]范围内。
    链表元素在[0, 20000]范围内。

进阶：
	如果不得使用临时缓冲区，该怎么解决？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"

	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func removeDuplicateNodes(head *ListNode) *ListNode {
	return method1(head)
}

func method1(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	mapper := make(map[int]*ListNode)
	slice := make([]int, 0)
	sentinel := &ListNode{Val:-1}

	pointer := head
	for pointer != nil {
		next := pointer.Next
		if _, ok := mapper[pointer.Val]; !ok {
			mapper[pointer.Val] = pointer
			mapper[pointer.Val].Next = nil
			slice = append(slice, pointer.Val)
		}

		pointer = next
	}

	pointer = sentinel
	for _, v := range slice {
		pointer.Next = mapper[v]
		pointer = pointer.Next
	}

	return sentinel.Next
}

func method2(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	occurred := map[int]bool{
		head.Val: true,
	}

	position := head
	for position.Next != nil {
		if !occurred[position.Next.Val] {
			occurred[position.Next.Val] = true
			position = position.Next
		} else {
			position.Next = position.Next.Next
		}
	}

	position.Next = nil
	return head
}

func method3(head *ListNode) *ListNode {
	p1 := head
	for p1 != nil {
		p2 := p1
		for p2.Next != nil {
			if p2.Next.Val == p1.Val {
				p2.Next = p2.Next.Next
			} else {
				p2 = p2.Next
			}
		}

		p1 = p1.Next
	}

	return head
}

func main() {
	head := ds.BuildSinglyLinkedList([]int{1,4,1,2})
	fmt.Println(head.ToList())
	fmt.Println(removeDuplicateNodes(head).ToList())
	fmt.Println(method3(head).ToList())
}
